﻿public class Solution {
    public int Trap(int[] height)
    {
        int res = 0;
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < height.Length; i++)
        {
            while (stack.Count > 0)
            {
                int top = stack.Peek();
                if (height[top] == height[i])
                {
                    stack.Pop();
                    break;
                }
                if (height[top] < height[i])
                {
                    int mid = stack.Pop();
                    if (stack.Count > 0)
                    {
                        top = stack.Peek();
                        int rightH = height[i];
                        int leftH = height[top];

                        int h = Math.Min(leftH, rightH) - height[mid];
                        int w = i - top - 1;
                        res += h * w;
                    }
                }
                else break;
            }
            stack.Push(i);
        }
        return res;
    }

    public static void Main(string[] args)
    {
        int[] height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

        Solution solution = new Solution();
        int res = solution.Trap(height);
        Console.WriteLine(res);
    }
}